/*******************************************************************************
 * Copyright (c) 2009 Luaj.org. All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 ******************************************************************************/
package org.luaj.vm2;

import java.io.Serializable;
import java.lang.ref.WeakReference;
import java.util.Vector;

/**
 * Subclass of {@link LuaValue} for representing lua tables.
 * <p>
 * Almost all API's implemented in {@link LuaTable} are defined and documented in {@link LuaValue}.
 * <p>
 * If a table is needed, the one of the type-checking functions can be used such as
 * {@link #istable()},
 * {@link #checktable()}, or
 * {@link #opttable(LuaTable)}
 * <p>
 * The main table operations are defined on {@link LuaValue}
 * for getting and setting values with and without metatag processing:
 * <ul>
 * <li>{@link #get(LuaValue)}</li>
 * <li>{@link #set(LuaValue, LuaValue)}</li>
 * <li>{@link #rawget(LuaValue)}</li>
 * <li>{@link #rawset(LuaValue, LuaValue)}</li>
 * <li>plus overloads such as {@link #get(String)}, {@link #get(int)}, and so on</li>
 * </ul>
 * <p>
 * To iterate over key-value pairs from Java, use
 * <pre> {@code
 * LuaValue k = LuaValue.NIL;
 * while ( true ) {
 *    Varargs n = table.next(k);
 *    if ( (k = n.arg1()).isnil() )
 *       break;
 *    LuaValue v = n.arg(2)
 *    process( k, v )
 * }}</pre>
 * <p>
 * <p>
 * As with other types, {@link LuaTable} instances should be constructed via one of the table constructor
 * methods on {@link LuaValue}:
 * <ul>
 * <li>{@link LuaValue#tableOf()} empty table</li>
 * <li>{@link LuaValue#tableOf(int, int)} table with capacity</li>
 * <li>{@link LuaValue#listOf(LuaValue[])} initialize array part</li>
 * <li>{@link LuaValue#listOf(LuaValue[], Varargs)} initialize array part</li>
 * <li>{@link LuaValue#tableOf(LuaValue[])} initialize named hash part</li>
 * <li>{@link LuaValue#tableOf(Varargs, int)} initialize named hash part</li>
 * <li>{@link LuaValue#tableOf(LuaValue[], LuaValue[])} initialize array and named parts</li>
 * <li>{@link LuaValue#tableOf(LuaValue[], LuaValue[], Varargs)} initialize array and named parts</li>
 * </ul>
 *
 * @see LuaValue
 */
public class LuaTable extends LuaValue implements Metatable, Serializable {
    
    static int MIN_HASH_CAPACITY = 2;
    static LuaString N = valueOf("n");

    /**
     * the array values
     */
    protected LuaValue[] array;

    /**
     * the hash part
     */
    Slot[] hash;

    /**
     * the number of hash entries
     */
    int hashEntries;

    /**
     * metatable for this table, or null
     */
    Metatable m_metatable;

    /**
     * Construct empty table
     */
    public LuaTable() {
        array = NOVALS;
        hash = NOBUCKETS;
    }

    /**
     * Construct table with preset capacity.
     *
     * @param narray capacity of array part
     * @param nhash  capacity of hash part
     */
    public LuaTable(int narray, int nhash) {
        presize(narray, nhash);
    }

    /**
     * Construct table with named and unnamed parts.
     *
     * @param named   Named elements in order {@code key-a, value-a, key-b, value-b, ... }
     * @param unnamed Unnamed elements in order {@code value-1, value-2, ... }
     * @param lastarg Additional unnamed values beyond {@code unnamed.length}
     */
    public LuaTable(LuaValue[] named, LuaValue[] unnamed, Varargs lastarg) {
        int nn = (named != null ? named.length : 0);
        int nu = (unnamed != null ? unnamed.length : 0);
        int nl = (lastarg != null ? lastarg.narg() : 0);
        presize(nu + nl, nn >> 1);
        for (int i = 0; i < nu; i++)
            rawset(i + 1, unnamed[i]);
        if (lastarg != null)
            for (int i = 1, n = lastarg.narg(); i <= n; ++i)
                rawset(nu + i, lastarg.arg(i));
        for (int i = 0; i < nn; i += 2)
            if (!named[i + 1].isnil())
                rawset(named[i], named[i + 1]);
    }

    /**
     * Construct table of unnamed elements.
     *
     * @param varargs Unnamed elements in order {@code value-1, value-2, ... }
     */
    public LuaTable(Varargs varargs) {
        this(varargs, 1);
    }

    /**
     * Construct table of unnamed elements.
     *
     * @param varargs  Unnamed elements in order {@code value-1, value-2, ... }
     * @param firstarg the index in varargs of the first argument to include in the table
     */
    public LuaTable(Varargs varargs, int firstarg) {
        int nskip = firstarg - 1;
        int n = Math.max(varargs.narg() - nskip, 0);
        presize(n, 1);
        set(N, valueOf(n));
        for (int i = 1; i <= n; i++)
            set(i, varargs.arg(i + nskip));
    }

    public int type() {
        return LuaValue.TTABLE;
    }

    public String typename() {
        return "table";
    }

    public boolean istable() {
        return true;
    }

    public LuaTable checktable() {
        return this;
    }

    public LuaTable opttable(LuaTable defval) {
        return this;
    }

    public void presize(int narray) {
        if (narray > array.length)
            array = resize(array, 1 << log2(narray));
    }

    void presize(int narray, int nhash) {
        if (nhash > 0 && nhash < MIN_HASH_CAPACITY)
            nhash = MIN_HASH_CAPACITY;
        // Size of both parts must be a power of two.
        array = (narray > 0 ? new LuaValue[1 << log2(narray)] : NOVALS);
        hash = (nhash > 0 ? new Slot[1 << log2(nhash)] : NOBUCKETS);
        hashEntries = 0;
    }

    /**
     * Resize the table
     */
    static LuaValue[] resize(LuaValue[] old, int n) {
        LuaValue[] v = new LuaValue[n];
        System.arraycopy(old, 0, v, 0, old.length);
        return v;
    }

    /**
     * Get the length of the array part of the table.
     *
     * @return length of the array part, does not relate to count of objects in the table.
     */
    int getArrayLength() {
        return array.length;
    }

    /**
     * Get the length of the hash part of the table.
     *
     * @return length of the hash part, does not relate to count of objects in the table.
     */
    int getHashLength() {
        return hash.length;
    }

    public LuaValue getmetatable() {
        return (m_metatable != null) ? m_metatable.toLuaValue() : null;
    }

    public LuaValue setmetatable(LuaValue metatable) {
        boolean hadWeakKeys = m_metatable != null && m_metatable.useWeakKeys();
        boolean hadWeakValues = m_metatable != null && m_metatable.useWeakValues();
        m_metatable = metatableOf(metatable);
        if ((hadWeakKeys != (m_metatable != null && m_metatable.useWeakKeys())) ||
                (hadWeakValues != (m_metatable != null && m_metatable.useWeakValues()))) {
            // force a rehash
            rehash(0);
        }
        return this;
    }

    public LuaValue get(int key) {
        LuaValue v = rawget(key);
        return v.isnil() && m_metatable != null ? gettable(this, valueOf(key)) : v;
    }

    public LuaValue get(LuaValue key) {
        LuaValue v = rawget(key);
        return v.isnil() && m_metatable != null ? gettable(this, key) : v;
    }

    public LuaValue rawget(int key) {
        if (key > 0 && key <= array.length) {
            LuaValue v = m_metatable == null ? array[key - 1] : m_metatable.arrayget(array, key - 1);
            return v != null ? v : NIL;
        }
        return hashget(LuaInteger.valueOf(key));
    }

    public LuaValue rawget(LuaValue key) {
        if (key.isinttype()) {
            int ikey = key.toint();
            if (ikey > 0 && ikey <= array.length) {
                LuaValue v = m_metatable == null
                        ? array[ikey - 1] : m_metatable.arrayget(array, ikey - 1);
                return v != null ? v : NIL;
            }
        }
        return hashget(key);
    }

    LuaValue hashget(LuaValue key) {
        if (hashEntries > 0) {
            for (Slot slot = hash[hashSlot(key)]; slot != null; slot = slot.rest()) {
                StrongSlot foundSlot;
                if ((foundSlot = slot.find(key)) != null) {
                    return foundSlot.value();
                }
            }
        }
        return NIL;
    }

    public void set(int key, LuaValue value) {
        if (m_metatable == null || !rawget(key).isnil() || !settable(this, LuaInteger.valueOf(key), value))
            rawset(key, value);
    }

    /**
     * caller must ensure key is not nil
     */
    public void set(LuaValue key, LuaValue value) {
        if (!key.isvalidkey() && !metatag(NEWINDEX).isfunction())
            typerror("table index");
        if (m_metatable == null || !rawget(key).isnil() || !settable(this, key, value))
            rawset(key, value);
    }

    public void rawset(int key, LuaValue value) {
        if (!arrayset(key, value))
            hashset(LuaInteger.valueOf(key), value);
    }

    /**
     * caller must ensure key is not nil
     */
    public void rawset(LuaValue key, LuaValue value) {
        if (!key.isinttype() || !arrayset(key.toint(), value))
            hashset(key, value);
    }

    /**
     * Set an array element
     */
    boolean arrayset(int key, LuaValue value) {
        if (key > 0 && key <= array.length) {
            array[key - 1] = value.isnil() ? null :
                    (m_metatable != null ? m_metatable.wrap(value) : value);
            return true;
        }
        return false;
    }

    /**
     * Remove the element at a position in a list-table
     *
     * @param pos the position to remove
     * @return The removed item, or {@link #NONE} if not removed
     */
    public LuaValue remove(int pos) {
        int n = length();
        if (pos == 0)
            pos = n;
        else if (pos > n)
            return NONE;
        LuaValue v = rawget(pos);
        for (LuaValue r = v; !r.isnil(); ) {
            r = rawget(pos + 1);
            rawset(pos++, r);
        }
        return v.isnil() ? NONE : v;
    }

    /**
     * Insert an element at a position in a list-table
     *
     * @param pos   the position to remove
     * @param value The value to insert
     */
    public void insert(int pos, LuaValue value) {
        if (pos == 0)
            pos = length() + 1;
        while (!value.isnil()) {
            LuaValue v = rawget(pos);
            rawset(pos++, value);
            value = v;
        }
    }

    /**
     * Concatenate the contents of a table efficiently, using {@link Buffer}
     *
     * @param sep {@link LuaString} separater to apply between elements
     * @param i   the first element index
     * @param j   the last element index, inclusive
     * @return {@link LuaString} value of the concatenation
     */
    public LuaValue concat(LuaString sep, int i, int j) {
        Buffer sb = new Buffer();
        if (i <= j) {
            sb.append(get(i).checkstring());
            while (++i <= j) {
                sb.append(sep);
                sb.append(get(i).checkstring());
            }
        }
        return sb.tostring();
    }

    public int length() {
        int a = getArrayLength();
        int n = a + 1, m = 0;
        while (!rawget(n).isnil()) {
            m = n;
            n += a + getHashLength() + 1;
        }
        while (n > m + 1) {
            int k = (n + m) / 2;
            if (!rawget(k).isnil())
                m = k;
            else
                n = k;
        }
        return m;
    }

    public LuaValue len() {
        return LuaInteger.valueOf(length());
    }

    public int rawlen() {
        return length();
    }

    /**
     * Get the next element after a particular key in the table
     *
     * @return key, value or nil
     */
    public Varargs next(LuaValue key) {
        int i = 0;
        do {
            // find current key index
            if (!key.isnil()) {
                if (key.isinttype()) {
                    i = key.toint();
                    if (i > 0 && i <= array.length) {
                        break;
                    }
                }
                if (hash.length == 0)
                    error("invalid key to 'next'");
                i = hashSlot(key);
                boolean found = false;
                for (Slot slot = hash[i]; slot != null; slot = slot.rest()) {
                    if (found) {
                        StrongSlot nextEntry = slot.first();
                        if (nextEntry != null) {
                            return nextEntry.toVarargs();
                        }
                    } else if (slot.keyeq(key)) {
                        found = true;
                    }
                }
                if (!found) {
                    error("invalid key to 'next'");
                }
                i += 1 + array.length;
            }
        } while (false);

        // check array part
        for (; i < array.length; ++i) {
            if (array[i] != null) {
                LuaValue value = m_metatable == null ? array[i] : m_metatable.arrayget(array, i);
                if (value != null) {
                    return varargsOf(LuaInteger.valueOf(i + 1), value);
                }
            }
        }

        // check hash part
        for (i -= array.length; i < hash.length; ++i) {
            Slot slot = hash[i];
            while (slot != null) {
                StrongSlot first = slot.first();
                if (first != null)
                    return first.toVarargs();
                slot = slot.rest();
            }
        }

        // nothing found, push nil, return nil.
        return NIL;
    }

    /**
     * Get the next element after a particular key in the
     * contiguous array part of a table
     *
     * @return key, value or none
     */
    public Varargs inext(LuaValue key) {
        int k = key.checkint() + 1;
        LuaValue v = rawget(k);
        return v.isnil() ? NONE : varargsOf(LuaInteger.valueOf(k), v);
    }

    /**
     * Set a hashtable value
     *
     * @param key   key to set
     * @param value value to set
     */
    void hashset(LuaValue key, LuaValue value) {
        if (value.isnil())
            hashRemove(key);
        else {
            int index = 0;
            if (hash.length > 0) {
                index = hashSlot(key);
                for (Slot slot = hash[index]; slot != null; slot = slot.rest()) {
                    StrongSlot foundSlot;
                    if ((foundSlot = slot.find(key)) != null) {
                        hash[index] = hash[index].set(foundSlot, value);
                        return;
                    }
                }
            }
            if (checkLoadFactor()) {
                if (key.isinttype() && key.toint() > 0) {
                    // a rehash might make room in the array portion for this key.
                    rehash(key.toint());
                    if (arrayset(key.toint(), value))
                        return;
                } else {
                    rehash(-1);
                }
                index = hashSlot(key);
            }
            Slot entry = (m_metatable != null)
                    ? m_metatable.entry(key, value)
                    : defaultEntry(key, value);
            hash[index] = (hash[index] != null) ? hash[index].add(entry) : entry;
            ++hashEntries;
        }
    }

    static int hashpow2(int hashCode, int mask) {
        return hashCode & mask;
    }

    static int hashmod(int hashCode, int mask) {
        return (hashCode & 0x7FFFFFFF) % mask;
    }

    /**
     * Find the hashtable slot index to use.
     *
     * @param key      the key to look for
     * @param hashMask N-1 where N is the number of hash slots (must be power of 2)
     * @return the slot index
     */
    static int hashSlot(LuaValue key, int hashMask) {
        switch (key.type()) {
            case TNUMBER:
            case TTABLE:
            case TTHREAD:
            case TLIGHTUSERDATA:
            case TUSERDATA:
                return hashmod(key.hashCode(), hashMask);
            default:
                return hashpow2(key.hashCode(), hashMask);
        }
    }

    /**
     * Find the hashtable slot to use
     *
     * @param key key to look for
     * @return slot to use
     */
    int hashSlot(LuaValue key) {
        return hashSlot(key, hash.length - 1);
    }

    void hashRemove(LuaValue key) {
        if (hash.length > 0) {
            int index = hashSlot(key);
            for (Slot slot = hash[index]; slot != null; slot = slot.rest()) {
                StrongSlot foundSlot;
                if ((foundSlot = slot.find(key)) != null) {
                    hash[index] = hash[index].remove(foundSlot);
                    --hashEntries;
                    return;
                }
            }
        }
    }

    boolean checkLoadFactor() {
        return hashEntries >= hash.length;
    }

    int countHashKeys() {
        int keys = 0;
        for (int i = 0; i < hash.length; ++i) {
            for (Slot slot = hash[i]; slot != null; slot = slot.rest()) {
                if (slot.first() != null)
                    keys++;
            }
        }
        return keys;
    }

    void dropWeakArrayValues() {
        for (int i = 0; i < array.length; ++i) {
            m_metatable.arrayget(array, i);
        }
    }

    int countIntKeys(int[] nums) {
        int total = 0;
        int i = 1;

        // Count integer keys in array part
        for (int bit = 0; bit < 31; ++bit) {
            if (i > array.length)
                break;
            int j = Math.min(array.length, 1 << bit);
            int c = 0;
            while (i <= j) {
                if (array[i++ - 1] != null)
                    c++;
            }
            nums[bit] = c;
            total += c;
        }

        // Count integer keys in hash part
        for (i = 0; i < hash.length; ++i) {
            for (Slot s = hash[i]; s != null; s = s.rest()) {
                int k;
                if ((k = s.arraykey(Integer.MAX_VALUE)) > 0) {
                    nums[log2(k)]++;
                    total++;
                }
            }
        }

        return total;
    }

    // Compute ceil(log2(x))
    static int log2(int x) {
        int lg = 0;
        x -= 1;
        if (x < 0)
            // 2^(-(2^31)) is approximately 0
            return Integer.MIN_VALUE;
        if ((x & 0xFFFF0000) != 0) {
            lg = 16;
            x >>>= 16;
        }
        if ((x & 0xFF00) != 0) {
            lg += 8;
            x >>>= 8;
        }
        if ((x & 0xF0) != 0) {
            lg += 4;
            x >>>= 4;
        }
        switch (x) {
            case 0x0:
                return 0;
            case 0x1:
                lg += 1;
                break;
            case 0x2:
                lg += 2;
                break;
            case 0x3:
                lg += 2;
                break;
            case 0x4:
                lg += 3;
                break;
            case 0x5:
                lg += 3;
                break;
            case 0x6:
                lg += 3;
                break;
            case 0x7:
                lg += 3;
                break;
            case 0x8:
                lg += 4;
                break;
            case 0x9:
                lg += 4;
                break;
            case 0xA:
                lg += 4;
                break;
            case 0xB:
                lg += 4;
                break;
            case 0xC:
                lg += 4;
                break;
            case 0xD:
                lg += 4;
                break;
            case 0xE:
                lg += 4;
                break;
            case 0xF:
                lg += 4;
                break;
        }
        return lg;
    }

    /*
     * newKey > 0 is next key to insert
     * newKey == 0 means number of keys not changing (__mode changed)
     * newKey < 0 next key will go in hash part
     */
    void rehash(int newKey) {
        if (m_metatable != null && (m_metatable.useWeakKeys() || m_metatable.useWeakValues())) {
            // If this table has weak entries, hashEntries is just an upper bound.
            hashEntries = countHashKeys();
            if (m_metatable.useWeakValues()) {
                dropWeakArrayValues();
            }
        }
        int[] nums = new int[32];
        int total = countIntKeys(nums);
        if (newKey > 0) {
            total++;
            nums[log2(newKey)]++;
        }

        // Choose N such that N <= sum(nums[0..log(N)]) < 2N
        int keys = nums[0];
        int newArraySize = 0;
        for (int log = 1; log < 32; ++log) {
            keys += nums[log];
            if (total * 2 < 1 << log) {
                // Not enough integer keys.
                break;
            } else if (keys >= (1 << (log - 1))) {
                newArraySize = 1 << log;
            }
        }

        LuaValue[] oldArray = array;
        Slot[] oldHash = hash;
        LuaValue[] newArray;
        Slot[] newHash;

        // Copy existing array entries and compute number of moving entries.
        int movingToArray = 0;
        if (newKey > 0 && newKey <= newArraySize) {
            movingToArray--;
        }
        if (newArraySize != oldArray.length) {
            newArray = new LuaValue[newArraySize];
            if (newArraySize > oldArray.length) {
                for (int i = log2(oldArray.length + 1), j = log2(newArraySize) + 1; i < j; ++i) {
                    movingToArray += nums[i];
                }
            } else if (oldArray.length > newArraySize) {
                for (int i = log2(newArraySize + 1), j = log2(oldArray.length) + 1; i < j; ++i) {
                    movingToArray -= nums[i];
                }
            }
            System.arraycopy(oldArray, 0, newArray, 0, Math.min(oldArray.length, newArraySize));
        } else {
            newArray = array;
        }

        int newHashSize = hashEntries - movingToArray
                + ((newKey < 0 || newKey > newArraySize) ? 1 : 0); // Make room for the new entry
        int oldCapacity = oldHash.length;
        int newCapacity;
        int newHashMask;

        if (newHashSize > 0) {
            // round up to next power of 2.
            newCapacity = (newHashSize < MIN_HASH_CAPACITY)
                    ? MIN_HASH_CAPACITY
                    : 1 << log2(newHashSize);
            newHashMask = newCapacity - 1;
            newHash = new Slot[newCapacity];
        } else {
            newCapacity = 0;
            newHashMask = 0;
            newHash = NOBUCKETS;
        }

        // Move hash buckets
        for (int i = 0; i < oldCapacity; ++i) {
            for (Slot slot = oldHash[i]; slot != null; slot = slot.rest()) {
                int k;
                if ((k = slot.arraykey(newArraySize)) > 0) {
                    StrongSlot entry = slot.first();
                    if (entry != null)
                        newArray[k - 1] = entry.value();
                } else {
                    int j = slot.keyindex(newHashMask);
                    newHash[j] = slot.relink(newHash[j]);
                }
            }
        }

        // Move array values into hash portion
        for (int i = newArraySize; i < oldArray.length; ) {
            LuaValue v;
            if ((v = oldArray[i++]) != null) {
                int slot = hashmod(LuaInteger.hashCode(i), newHashMask);
                Slot newEntry;
                if (m_metatable != null) {
                    newEntry = m_metatable.entry(valueOf(i), v);
                    if (newEntry == null)
                        continue;
                } else {
                    newEntry = defaultEntry(valueOf(i), v);
                }
                newHash[slot] = (newHash[slot] != null)
                        ? newHash[slot].add(newEntry) : newEntry;
            }
        }

        hash = newHash;
        array = newArray;
        hashEntries -= movingToArray;
    }

    public Slot entry(LuaValue key, LuaValue value) {
        return defaultEntry(key, value);
    }

    static boolean isLargeKey(LuaValue key) {
        switch (key.type()) {
            case TSTRING:
                return key.rawlen() > LuaString.RECENT_STRINGS_MAX_LENGTH;
            case TNUMBER:
            case TBOOLEAN:
                return false;
            default:
                return true;
        }
    }

    static Entry defaultEntry(LuaValue key, LuaValue value) {
        if (key.isinttype()) {
            return new IntKeyEntry(key.toint(), value);
        } else if (value.type() == TNUMBER) {
            return new NumberValueEntry(key, value.todouble());
        } else {
            return new NormalEntry(key, value);
        }
    }

    // ----------------- sort support -----------------------------
    //
    // implemented heap sort from wikipedia
    //
    // Only sorts the contiguous array part.
    //

    /**
     * Sort the table using a comparator.
     *
     * @param comparator {@link LuaValue} to be called to compare elements.
     */
    public void sort(LuaValue comparator) {
        if (m_metatable != null && m_metatable.useWeakValues()) {
            dropWeakArrayValues();
        }
        int n = array.length;
        while (n > 0 && array[n - 1] == null)
            --n;
        if (n > 1)
            heapSort(n, comparator);
    }

    void heapSort(int count, LuaValue cmpfunc) {
        heapify(count, cmpfunc);
        for (int end = count - 1; end > 0; ) {
            swap(end, 0);
            siftDown(0, --end, cmpfunc);
        }
    }

    void heapify(int count, LuaValue cmpfunc) {
        for (int start = count / 2 - 1; start >= 0; --start)
            siftDown(start, count - 1, cmpfunc);
    }

    void siftDown(int start, int end, LuaValue cmpfunc) {
        for (int root = start; root * 2 + 1 <= end; ) {
            int child = root * 2 + 1;
            if (child < end && compare(child, child + 1, cmpfunc))
                ++child;
            if (compare(root, child, cmpfunc)) {
                swap(root, child);
                root = child;
            } else
                return;
        }
    }

    boolean compare(int i, int j, LuaValue cmpfunc) {
        LuaValue a, b;
        if (m_metatable == null) {
            a = array[i];
            b = array[j];
        } else {
            a = m_metatable.arrayget(array, i);
            b = m_metatable.arrayget(array, j);
        }
        if (a == null || b == null)
            return false;
        if (!cmpfunc.isnil()) {
            return cmpfunc.call(a, b).toboolean();
        } else {
            return a.lt_b(b);
        }
    }

    void swap(int i, int j) {
        LuaValue a = array[i];
        array[i] = array[j];
        array[j] = a;
    }

    /**
     * This may be deprecated in a future release.
     * It is recommended to count via iteration over next() instead
     *
     * @return count of keys in the table
     */
    public int keyCount() {
        LuaValue k = LuaValue.NIL;
        for (int i = 0; true; i++) {
            Varargs n = next(k);
            if ((k = n.arg1()).isnil())
                return i;
        }
    }

    /**
     * This may be deprecated in a future release.
     * It is recommended to use next() instead
     *
     * @return array of keys in the table
     */
    public LuaValue[] keys() {
        Vector l = new Vector();
        LuaValue k = LuaValue.NIL;
        while (true) {
            Varargs n = next(k);
            if ((k = n.arg1()).isnil())
                break;
            l.addElement(k);
        }
        LuaValue[] a = new LuaValue[l.size()];
        l.copyInto(a);
        return a;
    }

    // equality w/ metatable processing
    public LuaValue eq(LuaValue val) {
        return eq_b(val) ? TRUE : FALSE;
    }

    public boolean eq_b(LuaValue val) {
        if (this == val) return true;
        if (m_metatable == null || !val.istable()) return false;
        LuaValue valmt = val.getmetatable();
        return valmt != null && LuaValue.eqmtcall(this, m_metatable.toLuaValue(), val, valmt);
    }

    /**
     * Unpack all the elements of this table
     */
    public Varargs unpack() {
        return unpack(1, this.length());
    }

    /**
     * Unpack all the elements of this table from element i
     */
    public Varargs unpack(int i) {
        return unpack(i, this.length());
    }

    /**
     * Unpack the elements from i to j inclusive
     */
    public Varargs unpack(int i, int j) {
        int n = j + 1 - i;
        switch (n) {
            case 0:
                return NONE;
            case 1:
                return get(i);
            case 2:
                return varargsOf(get(i), get(i + 1));
            default:
                if (n < 0)
                    return NONE;
                LuaValue[] v = new LuaValue[n];
                while (--n >= 0)
                    v[n] = get(i + n);
                return varargsOf(v);
        }
    }

    /**
     * Represents a slot in the hash table.
     */
    interface Slot {

        /**
         * Return hash{pow2,mod}( first().key().hashCode(), sizeMask )
         */
        int keyindex(int hashMask);

        /**
         * Return first Entry, if still present, or null.
         */
        StrongSlot first();

        /**
         * Compare given key with first()'s key; return first() if equal.
         */
        StrongSlot find(LuaValue key);

        /**
         * Compare given key with first()'s key; return true if equal. May
         * return true for keys no longer present in the table.
         */
        boolean keyeq(LuaValue key);

        /**
         * Return rest of elements
         */
        Slot rest();

        /**
         * Return first entry's key, iff it is an integer between 1 and max,
         * inclusive, or zero otherwise.
         */
        int arraykey(int max);

        /**
         * Set the value of this Slot's first Entry, if possible, or return a
         * new Slot whose first entry has the given value.
         */
        Slot set(StrongSlot target, LuaValue value);

        /**
         * Link the given new entry to this slot.
         */
        Slot add(Slot newEntry);

        /**
         * Return a Slot with the given value set to nil; must not return null
         * for next() to behave correctly.
         */
        Slot remove(StrongSlot target);

        /**
         * Return a Slot with the same first key and value (if still present)
         * and rest() equal to rest.
         */
        Slot relink(Slot rest);
    }

    /**
     * Subclass of Slot guaranteed to have a strongly-referenced key and value,
     * to support weak tables.
     */
    interface StrongSlot extends Slot {
        /**
         * Return first entry's key
         */
        LuaValue key();

        /**
         * Return first entry's value
         */
        LuaValue value();

        /**
         * Return varargsOf(key(), value()) or equivalent
         */
        Varargs toVarargs();
    }

    static class LinkSlot implements StrongSlot {
        Entry entry;
        Slot next;

        LinkSlot(Entry entry, Slot next) {
            this.entry = entry;
            this.next = next;
        }

        public LuaValue key() {
            return entry.key();
        }

        public int keyindex(int hashMask) {
            return entry.keyindex(hashMask);
        }

        public LuaValue value() {
            return entry.value();
        }

        public Varargs toVarargs() {
            return entry.toVarargs();
        }

        public StrongSlot first() {
            return entry;
        }

        public StrongSlot find(LuaValue key) {
            return entry.keyeq(key) ? this : null;
        }

        public boolean keyeq(LuaValue key) {
            return entry.keyeq(key);
        }

        public Slot rest() {
            return next;
        }

        public int arraykey(int max) {
            return entry.arraykey(max);
        }

        public Slot set(StrongSlot target, LuaValue value) {
            if (target == this) {
                entry = entry.set(value);
                return this;
            } else {
                return setnext(next.set(target, value));
            }
        }

        public Slot add(Slot entry) {
            return setnext(next.add(entry));
        }

        public Slot remove(StrongSlot target) {
            if (this == target) {
                return new DeadSlot(key(), next);
            } else {
                this.next = next.remove(target);
            }
            return this;
        }

        public Slot relink(Slot rest) {
            // This method is (only) called during rehash, so it must not change this.next.
            return (rest != null) ? new LinkSlot(entry, rest) : (Slot) entry;
        }

        // this method ensures that this.next is never set to null.
        Slot setnext(Slot next) {
            if (next != null) {
                this.next = next;
                return this;
            } else {
                return entry;
            }
        }

        public String toString() {
            return entry + "; " + next;
        }
    }

    /**
     * Base class for regular entries.
     * <p>
     * <p>
     * If the key may be an integer, the {@link #arraykey(int)} method must be
     * overridden to handle that case.
     */
    static abstract class Entry extends Varargs implements StrongSlot {
        public abstract LuaValue key();

        public abstract LuaValue value();

        abstract Entry set(LuaValue value);

        public int arraykey(int max) {
            return 0;
        }

        public LuaValue arg(int i) {
            switch (i) {
                case 1:
                    return key();
                case 2:
                    return value();
            }
            return NIL;
        }

        public int narg() {
            return 2;
        }

        /**
         * Subclasses should redefine as "return this;" whenever possible.
         */
        public Varargs toVarargs() {
            return varargsOf(key(), value());
        }

        public LuaValue arg1() {
            return key();
        }

        public Varargs subargs(int start) {
            switch (start) {
                case 1:
                    return this;
                case 2:
                    return value();
            }
            return NONE;
        }

        public StrongSlot first() {
            return this;
        }

        public Slot rest() {
            return null;
        }

        public StrongSlot find(LuaValue key) {
            return keyeq(key) ? this : null;
        }

        public Slot set(StrongSlot target, LuaValue value) {
            return set(value);
        }

        public Slot add(Slot entry) {
            return new LinkSlot(this, entry);
        }

        public Slot remove(StrongSlot target) {
            return new DeadSlot(key(), null);
        }

        public Slot relink(Slot rest) {
            return (rest != null) ? new LinkSlot(this, rest) : (Slot) this;
        }
    }

    static class NormalEntry extends Entry {
        LuaValue key;
        LuaValue value;

        NormalEntry(LuaValue key, LuaValue value) {
            this.key = key;
            this.value = value;
        }

        public LuaValue key() {
            return key;
        }

        public LuaValue value() {
            return value;
        }

        public Entry set(LuaValue value) {
            this.value = value;
            return this;
        }

        public Varargs toVarargs() {
            return this;
        }

        public int keyindex(int hashMask) {
            return hashSlot(key, hashMask);
        }

        public boolean keyeq(LuaValue key) {
            return key.raweq(this.key);
        }
    }

    static class IntKeyEntry extends Entry {
        int key;
        LuaValue value;

        IntKeyEntry(int key, LuaValue value) {
            this.key = key;
            this.value = value;
        }

        public LuaValue key() {
            return valueOf(key);
        }

        public int arraykey(int max) {
            return (key >= 1 && key <= max) ? key : 0;
        }

        public LuaValue value() {
            return value;
        }

        public Entry set(LuaValue value) {
            this.value = value;
            return this;
        }

        public int keyindex(int mask) {
            return hashmod(LuaInteger.hashCode(key), mask);
        }

        public boolean keyeq(LuaValue key) {
            return key.raweq(this.key);
        }
    }

    /**
     * Entry class used with numeric values, but only when the key is not an integer.
     */
    static class NumberValueEntry extends Entry {
        double value;
        LuaValue key;

        NumberValueEntry(LuaValue key, double value) {
            this.key = key;
            this.value = value;
        }

        public LuaValue key() {
            return key;
        }

        public LuaValue value() {
            return valueOf(value);
        }

        public Entry set(LuaValue value) {
            LuaValue n = value.tonumber();
            if (!n.isnil()) {
                this.value = n.todouble();
                return this;
            } else {
                return new NormalEntry(this.key, value);
            }
        }

        public int keyindex(int mask) {
            return hashSlot(key, mask);
        }

        public boolean keyeq(LuaValue key) {
            return key.raweq(this.key);
        }
    }

    /**
     * A Slot whose value has been set to nil. The key is kept in a weak reference so that
     * it can be found by next().
     */
    static class DeadSlot implements Slot {

        Object key;
        Slot next;

        DeadSlot(LuaValue key, Slot next) {
            this.key = isLargeKey(key) ? new WeakReference(key) : (Object) key;
            this.next = next;
        }

        LuaValue key() {
            return (LuaValue) (key instanceof WeakReference ? ((WeakReference) key).get() : key);
        }

        public int keyindex(int hashMask) {
            // Not needed: this entry will be dropped during rehash.
            return 0;
        }

        public StrongSlot first() {
            return null;
        }

        public StrongSlot find(LuaValue key) {
            return null;
        }

        public boolean keyeq(LuaValue key) {
            LuaValue k = key();
            return k != null && key.raweq(k);
        }

        public Slot rest() {
            return next;
        }

        public int arraykey(int max) {
            return -1;
        }

        public Slot set(StrongSlot target, LuaValue value) {
            Slot next = (this.next != null) ? this.next.set(target, value) : null;
            if (key() != null) {
                // if key hasn't been garbage collected, it is still potentially a valid argument
                // to next(), so we can't drop this entry yet.
                this.next = next;
                return this;
            } else {
                return next;
            }
        }

        public Slot add(Slot newEntry) {
            return (next != null) ? next.add(newEntry) : newEntry;
        }

        public Slot remove(StrongSlot target) {
            if (key() != null) {
                next = next.remove(target);
                return this;
            } else {
                return next;
            }
        }

        public Slot relink(Slot rest) {
            return rest;
        }

        public String toString() {
            StringBuffer buf = new StringBuffer();
            buf.append("<dead");
            LuaValue k = key();
            if (k != null) {
                buf.append(": ");
                buf.append(k.toString());
            }
            buf.append('>');
            if (next != null) {
                buf.append("; ");
                buf.append(next.toString());
            }
            return buf.toString();
        }
    }

    ;

    static Slot[] NOBUCKETS = {};

    // Metatable operations

    public boolean useWeakKeys() {
        return false;
    }

    public boolean useWeakValues() {
        return false;
    }

    public LuaValue toLuaValue() {
        return this;
    }

    public LuaValue wrap(LuaValue value) {
        return value;
    }

    public LuaValue arrayget(LuaValue[] array, int index) {
        return array[index];
    }
}
